package com.algorithm.dijkstra;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import org.apache.commons.collections4.CollectionUtils;

import java.util.List;
import java.util.Map;

/**
 * 狄克斯特拉算法测试
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/11 6:46 下午
 */
public class DijkstraTest {

    public static void main(String[] args) {
        DijkstraTest d = new DijkstraTest();
        System.out.println(d.findBestPath());
    }

    private DijkstraNode data;

    public DijkstraTest() {
        DijkstraNode 钢琴1 = generateNode("钢琴", 20, null);
        DijkstraNode 钢琴2 = generateNode("钢琴", 10, null);

        DijkstraNode 低音吉他1 = generateNode("低音吉他", 15, Lists.newArrayList(钢琴1));
        DijkstraNode 低音吉他2 = generateNode("低音吉他", 30, Lists.newArrayList(钢琴1));

        DijkstraNode 架子鼓1 = generateNode("架子鼓", 20, Lists.newArrayList(钢琴2));
        DijkstraNode 架子鼓2 = generateNode("架子鼓", 35, Lists.newArrayList(钢琴2));

        DijkstraNode 海报 = generateNode("海报", 0, Lists.newArrayList(架子鼓2,低音吉他2));
        DijkstraNode 黑胶唱片 = generateNode("黑胶唱片", 5, Lists.newArrayList(架子鼓1,低音吉他1));

        this.data = generateNode("乐谱", 0, Lists.newArrayList(海报,黑胶唱片));
    }

    private DijkstraNode generateNode(String name, int cost, List<DijkstraNode> nodes) {
        return new DijkstraNode(name, cost, nodes);
    }
    private Map<String, Integer> cost = Maps.newHashMap();
    private Map<String, String> parents = Maps.newHashMap();

    private String findBestPath() {
        parseNode(data);
        // 全部解析完以后 parents里面存储的就是最小路径
        String key = "钢琴";
        StringBuilder path = new StringBuilder("钢琴");
        while (parents.get(key) != null) {
            key = parents.get(key);
            path.append("-").append(key);
        }
        path.append("-cost=").append(cost.get("钢琴"));
        return path.toString();
    }

    private void parseNode(DijkstraNode node) {
        List<DijkstraNode> nexts = node.getNexts();
        if (CollectionUtils.isEmpty(nexts)) {
            return;
        }
        Integer preCost = cost.getOrDefault(node.getName(), 0);
        nexts.forEach(n -> {
            // 目前到达当前节点的最小费用
            int currentCost = preCost + n.getCost();
            String nodeName = n.getName();
            Integer lastCost = cost.get(nodeName);
            if (lastCost == null || currentCost < lastCost) {
                // 更新最小花费
                cost.put(nodeName, currentCost);
                // 更新关联关系
                parents.put(n.getName(), node.getName());
            }
            parseNode(n);
        });
    }
}
